package com.xk._03真题骗._02链表;

import com.xk._03真题骗._00bean.ListNode;

/*
 * @description: https://leetcode.cn/problems/partition-list/
 * @author: xu
 * @date: 2022/10/27 20:40
 */
public class _86分隔链表 {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode lHead = new ListNode(0);
        ListNode lTail = lHead;
        ListNode rHead = new ListNode(0);
        ListNode rTail = rHead;
        while (head != null) {
            if (head.val < x) {
                lTail = lTail.next = head;
            } else {
                rTail = rTail.next = head;
            }
            head = head.next;
        }
        /*
        * 这句代码不能少
        * 因为可能会出现这样的情况：
        *   原链表倒数第N个结点A的值是>=x的，A后面所有的节点都是<x的
        *   然后rTail.next最终其实是A.next
        * */
        rTail.next = null;
        lTail.next = rHead.next;
        return lHead.next;
    }
}
